LA PROGRAMMATION LINÉ

UNIVERSITÉ POLYTECHIQUE BUCAREST

FACULTÉ DE GÉNIE EN LANGUES ÉTRENGÈRES

RECHERCHE SCIENTIFIQUE

PREMIER SEMESTRE

UN OUTIL UTILE:

LA PROGRAMMATION LINÉ

UN OUTIL UTILE:

LA PROGRAMMATION LINÉ

La programmation linéaire est la recherche extremum (maximum ou minimum) d’un fonction linéaire de n variables liées par un systÈme de m relations linéaires (équations ou inéquations) appelées contraintes.

Soit, avec les notatioms généralement usitées:

F= i = 1 à n

la fonction

et j = 1 à m

les contraines.

­­­­­­­­­­­­­­­­­­­­

On peut associer à l’ensemble des variables x_i un espace vectoriel à n dimensions qui contient en particulier les vecteurs solutions X.

Un certain nombre de problémes industriels de nature technico-économique relevant de la programmation linéaire.

C’est le cas, en particulier, chaque fois que l’on cherche à optimiser une fonction économique dont la dépendance vis-à-vis des variables inconnues du problÈme est de forme linéaire et que, par ailleurs, les mÊmes variables sont liées par des contraintes linéaires traduisant en general des limites de capacité.

Ainsi, dans une entreprise fabriquant plusieurs produits, la marge brute totale pour une période d’exploitation donnée est, dans certaines limites, une function linéaire des quantités fabriquées et vendues de ces différents produits.

Tandis que ces mÊmes quantités sont liées par des relations linéaires traduisant les limites de capacités de production (ou de ventes) de l’entreprise.

La programmation linéaire se rattache au probléme beaucoup plus général de la recherche d’extrema liés qui avait reçu une solution générale dÈs le XVIII^e siÈcle.

En effet, on sait qu’étant donné une function de n variables

f(x₁, x₂, ……….., x_n) = 0

liées par m relations

f₁ (x₁……………x_n) = 0 f_m (x₁………..x_n) = 0

pour trouver les extrema de f on adjoint aux m relations ci dessus les equations obtenues en égalant à zero les derives partielles de la function f + λ₁f₁+…..λ_mf_m

Les coefficients λ sont les multiplicateurs de LAGRANGE.

En principe, on disposait donc d’une méthode tout à fait générale et débordant d’ailleurs le cas particulier de la programmation linéaire pour résoudre cette classe de problÈmes. En fait, la méthode des multiplicateurs de LAGRANGE s’est révélée peu practicable. C’est pourquoi des recherches ont été conduites aprÈs la seconde guerre mondiale.

Ces recherche ont abouti au développement d’une méthode entiÈrement originale, proper à donner la solution du problÈme general de la programmation linéaire. Cette méthode est connue sous le nom de MÉTHODE du SIMPLEXE ou de DANTZIG.

D’autres méthodes ont été proposées mais la méthode de Dantzig demeure, de trÈs loin, la plus utilisée du fait, certainement, de son efficacité.

Formulation mathématique standard du problÈme.

Bien que la formulation mathématique donnée ci-dessus soit déjà trÈs simple, une formulation « standard » a été proposée afin d’unifier la méthode et de ramener tous les cas de resolution à un modÈle unique. (Certains auteurs réser vent l’appellation de « canonique » à cette forme, d’autres l’appellent « standard »).

A_SX_S = d X_S ≥ 0

minimiser f= C_S X_S

Les notations prenant les significations suivantes:

A_S il s’agit de la matrice des coefficients des équations ou inéquations de contraintes

X_S c’est le vecteur colonne à n composantes

X₁.X_n

d vecteur colonne du second membre à m composantes

C_S est le vecteur ligne de la fonction àmaximiser

On peut ramener toutes les formulations de problÈmes à cette forme standard dans la mesure oÙ:

Seules les valeurs positives des variables constituent des solutions possibles.

Les inéquations peuvent Être ramenées à des equations par l’introductin de variables supplémentaires, dites variables d’écarts.

Un changement de signe sur la function linéaire à optimizer peut toujours nous ramener au cas de la recherché d’un maximum (ou d’un minimum).

2. L’INTERPRÉTATION GÉOMÉTRIQUE

Le problÈme de la programmation linéaire reçoit une interprétation géométrique simple. En effet, les équations ou inéquations de contraintes linéaires représentent des droites, plans ou des hyperplans dans un espace à n dimensions ( n étant le nombre de variables). L’intersection de ces droites, plans, hyperplans définit un polygone, polyÈdre, hyperpolyÈdre, à l’intérieur duquel le systÈme des contraintes du problÈme se trouve satisfait.

Il s’agit alors de trouver, dans le domaine ainsi délimité, le ou les points qui optimisent la fonction. Cette interprétation est particuliÈrement simple dans le cas de deux variables seulement.

Soit, par exemple, la fonction à maximiser:

f = 3x₁ + 4x₂

et le systÈme de contraintes:

x₁ + 3x₂ 24

x₁ + 2x₂ 17

5x₁ + 3x₂ 54

x₁ + x₂ 0

Chacune des contraintes est représentée par une droite du plan xx qui partage le plan en deux régions: une régions oÙ la contrainte est satisfaite une région oÙ la contrainte n’est pas satisfaite ( la droite étant elle-mÊme le lieu des points pour lesqueles les conditions d’égalité des deux mambres est satisfaite).

L’ amsemble des droites représentant les contraintes délimite un polygone OABCD qui est le domaine à l’intérieur duquel doivent se trouver les valeurs de x₁x₂ pour que l’ensemble des contraintes soient satisfaites.

Nous devons chercher le ou les points de ce domaine qui maximise la fonction .

Z = 3x₁ + 4x₂

Pour cela, nous pouvons nous contenter de remarquer que la function à optimiser est une fonction linéaire de xx, donc une droite dont tous les points ont la particularité de correspondre à une mÊme valeur de Z, et cette valeur sera maxi pour la droite la plus éloignée de l’origine. Soit sur le sommet C du polygone qui représente donc la solution cherchée.

Ainsi, un problÈme de programmation linéaire à 2 variables x₁x₂ comportant un certain nombre d’inéquations de contraintes donne lieu à l’ interprétation géométrique suivante:

Dans le plan des variables x₁x₂ le domaine des points qui satisfont au systÈme d’inéquations de contraintes est limité par un polygone à l’intérieur duquel devront se trouver les solutions. La fonction économique est également représentée par une droite comportant un paramÈtre qui est précisément la valeur de la fonction à optimiser.

f = C₁x₁ + C x₂

de telle sorte que les points de la représentent l’ensamble des points du plan d’égale valeur économique (droite isoéconomique).

La droite isoéconomique de valeur nulle passe par l’origine.

Loersque Z prend des valeurs positives, la droite isoéconomique de valeur Z s’éloigne de l’ origine tout en restant parallÈle à la droite isoéconomique de valeur nulle.

La valeur du paramÈtre Z croit précisément comme la distance de la droite à l’origine.

La solution du problÈme se trouvera donc sur la droite parallÈle à la droite isoéconomique de valeur nulle et ayant au moins un points dans le polygone des contraintes.

Cette droite est, en général, une parallÈle à la droite isoéconomique de valeur nulle passant par l’un des somments du polygone.

Autrement dit, la solution se trouve en général Être l’un sommets du poly gone des contraintes.

On peut généraliser au cas de n variables:

- les droites deviennent des plans (n = 3) ou des hyperplans (n > 3)

- les polygones deviennent polyÈdres ou hyperpolyÈdres et la recherche de la solution consiste à chercher sur quel sommet du polyÈdre la fonction économique atteint son extremum.

Naturellement, le cas purra se présenter oÙ la droite isoéconomique sera paralléle à l’un des côtés du polygone des contraintes.

Dans ce cas, malgrétout exceptionnel, on aura, non pas un points comme solution, mais l’ensemble des points correspondants ai côté du polygone.

Figure. Résolution graphique d’un problem de programmation linéaire

3. EXEMPLE EN GESTION DE PRODUCTION

Soit une enterprise fabriquant un certain nombre de prodits P₁,P₂,P₃,…….P_n.

Pour ces fabrications l’enteprise utilize un certain nombre de moyens (machines, postes de travail manuel) M₁, M₂, M₃, ……….., M_m et de telle façon que plusieurs de ces moyens soient communs à plisieurs des produits.

Les moyens M₁, M₂, ……., M_m ont des capacités limitées ; par exemple, on dispose chaque mois de tant d’heures de M₁, de tant d’heures de M₂.

Soient C₁, C₂. .C_m les limites de capacité des moyens.

D’autre part, sont connues les marges dégagées par chacun des produits fabriqués P₁, P₂, …….

Le problÈme qui se pose à toute entreprise travaillant suivant ce schéma est alors le suivant:

Quel est le programme de production ( quantité produite par mois des différents produits: soit x₁ pour P₁, x₂ pour P₂) qui maximise la marge total?

La méthode de programmation linéaire autorise l’introduction d’autres types de contraintes, par exemple commerciales.

Supposons en effet que la capacité d’écoulement soit limitée, par exemple, à V_i pour le produit P_i

Il suffira d’introduire la contrainte supplémentaire

x_i (production de P_i) V_i

qui est encore une inéquation linéaire.

Pour traduire les limites de capacité des moyens, il sera nécessaire de connaitre le temps employé sur chacun des produits, autrement dit les « gammes » de fabrication.

1. Nous excluons donc le cas des fabrication du type par ligne de produits qui ne relÈve pas de la programmation linéaire.

Note techique

La méthode du Simplexe ou de Dantzig

ProblÈme de maximisation.

L’interprétation géométrique que nous avons rappelée ci-dessus, au paragraphe 2, va nous aider à comprendre la démarche de l’algorithme de Dantzig ou du Simplexe.

Ainsi que nous l’avons noté, la solution cherchée se trouve Être l’un des sommets de l’hyperpolyÈdre défini par le systÈme des contraintes.

Partant de cette remarque, la méthode va consister, par une série d’itérations successive, à cheminer de sommet en sommet en améliorant à chaque fois la valeur de la fonction économique jusqu’à l’obtention de l’optimum.

Naturellement , pour éviter trop de calculs, nous partirons d’un sommet aussi voisin que possible de la solution. Lorsqu’on ne connait pas un tel sommet, ce qui est souvent le cas, il sera toujours possible de partir de l’origine des coordonnées qui est elle aussi, rappelons-le, l’un des sommets de l’hyperpolyÈdre, le moins intéressant de tous, cependant, puisqu’à l’origine la fonction économique a une valeur nulle.

Tel est le principe de la méthode du Simplexe. Il reste à définir l’algorithme du calcul.

Nous commencerons par ramener le systÈme d’inéquationa linéaire à un systÈme ne comportant que comportant que des équations par l’introduction de variables d’écart.

m étant le nombre de contraintes, nous aurons à introduire au maximum m variables d’écart.

Ainsi, le systÈme pris en exemple au paragraphe 2 va s’écrire:

x₁ + 3x₂ + x₃ = 24

x ₁+ 2x₂ + x₄ = 17

5x₁ +3x₂ + x₅ =50

x₃, x₄, x₅ sont les variables d’écart qui nous ont permis de transformer le systÈme d’inéquations linéaires en un systéme linéaire d’équations.

De façon générale, le systÈme linéaire s’écrira sous forme matricielle:

AX = D

CX = f

X =

D =

C =

On appelle base B un ensemble de vecteurs colonnes a_j linéairement indépendants.

Les m variables correspondantes sont les variables de base du systÈme; les (n - m) autres variables sont les variables secondaires ou hors-base.

Si B est une base et que l’on annule les variables hors base du systÈme, on obtient un systÈme de Cramer don’t la solution est connue.

Cette solution est la solution de base associée à B.

Le passage d’un sommet de l’hyperpolyÈdre à un autre sommet voisin dans l’espace à m dimensions se fera en échangeant un vecteur de la base B avec un autre vecteur hors base.

Nous savons faire ce changement de base et nous servirons des formules de transformation bien connues en algebra linéaire pour calculer la nouvelle matrice des coefficients.

La disposition pratique des calcul se fait sous la forme d’un tableau, dit « tableau du Simplexe » , qui reproduit la matrice des coefficients du systÈme linéaire à laquelle on adjoint une ligne et une colonne marginales.

La ligne marginale représente les coefficients de la forme linéaire de la fonction économique, tandis que la colonne indiquera les noms des variables de la base.

Ainsi, pour le systÈme linéaire que nous avons pris en exemple, le tableau de départ du Simplexe se présentera de la façon suivante:

Le tableau correspond au systÈme d’équations linéaire suivant:

x₁ + 3x₂+ x₃ = 24

x₁ + 2x₂ + x₄ = 17

5x₁ + 3x₂ + x₅ = 50

et à la forme linéaire suivante de la function économique:

f = 3x + 4x

x , x , x sont les variables d’écart.

Nous voyons qu’elles constituent également les variables de la solution de base puisque nous les avons fait figurer dans la colonne de gauche qui indique précisément , suivant nos conventions, les variables de base.

En effet, puisque nous n’avons aucune connaissance a priori des coordonnées des sommets du polygone des contraintes, nous partons de la solution triviale:

x₁ x₃

x₂ x₄

x₅

qui correspond à l’origine des coordonnées.

La fonction économique correspondant àce point est évidemment nulle, ce que nous indiquons en faisant figurer la valeur 0 dans la case en haut et à droite du tableau.

Pour passer de l’origine à un autre sommet du polygone des contraintes, nous allons faire rentrer dans la base l’une des variables x₁ ou x₂ et, corrélativement, faire sortir l’une des variables d’écart x₃, x₄ ou x₅, variable dont la contribution à la fonction économique est nulle.

Le choix de la variable d’entrée se fera d’aprÈs la valeur du coefficient des variables dans la fonction économique.

C’est l’objet du premier critÈre du Simplexe:

La variable d’entrédans la base est celle dont le coefficient dans la fonction économique est le plus élevé.

Dans l’exemple traité, ce sera donc la variable x₂ qui va rentrer dans la nouvelle base.

Comment sélectionne – t – on la variable sortante?

Avant d’énoncer la rÈgle générale qui constitue le second critÈre du Simplexe, voyons comment se présente le problÈme dans notre exemple:

D’aprÈs ce qui vient d’Être dit, la nouvelle solution de base va comporter la variable x₂ et deux des trois variables d’écart x₃, x₄, x₅.

Nous aurons donc à satisfaire au systÈme suivant:

3x₂ + x₃ = 24

2x₂ + x₄ = 17

3x₂ + x₅ = 50

L’une des trois varibles x₃, x₄, x₅ nulle sera variable sortante de la base.

Or, il est facile de voir sur cet exemple simple que la seule solution possible est x₃ = 0 x₂ = 8

En effet, les deux autres équation donnent pour x₂ des valeurs supérieurs

et > = 8

ce qui conduirait à un x₃ < 0.

Cette considération se généralise dans le second critÈre du Simplexe:

La ligne qui va définir la variable sortante est celle pour laquelle le quotient des termes constants (les termes de la colonne de droite du tableau) par les coefficients de la variable entrante est le plus petit positif.

Dans l’exemple, c’est x₃.

Ainsi , la nouvelle base est définie par les variables x₂, x₄, x₅.

Nous cheminons donc depuis l’origine vers le sommet du polygone des contraintes situé sur x₂.

La nouvelle solution sera définie par le deuxiÈme tableau du Somplexe, qui se déduira par application des formules de transformation de l’algÈbre linéaire, dont l’application particuliÈre à la programmation linéaire donne lieu à la « rÈgle du pivot ».

Revenons à notre premier tableau, nous avons vu ( 1^er critÈre du Simplexe) que la variables entrante était x₂, et ( 2^e critÈre du Simplexe) que la variable sortante est x₃.

Le coefficient qui se trouve au croisement de la colonne de la variable entrante x₂ et de la ligne de la variable sortante x₃ est le « pivot » . Il va servir à calculer tous les autres coefficients du deuxiÈme tableau du Simplexe.

Nous transformons le tableau initial de tell façon que la variable entrante apparaisse dans la premiÈre colonne à la place de la variable sortante. Les variables absentes de la premiÈre colonne ( donc variables hors-base) sont nulles.

Nous substituons donc, dans la premiÈre colonne, x₂ à x₃.

Les nouvelles valeurs des coefficients tirées des formules de changement de base peuvent se résumer de la façon suivante:

Soit a_ij le pivot (ligne i, colonne j),

Les nouveaux coefficients de la colonne du pivot ( colonne j) sont tous nuls, sauf le pivot qui est égal à 1.

Les nouveaux coefficients de la ligne du pivot (ligne i) sont égaux aux anciens divisés par la valeur du pivot.

Un autre terme quelconque, soit a_kl ( ne figurant ni sur la ligne, ni sur la collone du pivot) est égal à son ancienne valeur a_kl moins le produit des termes rectangles constants a_kj et a_il divisés par le pivot.

Soit , suivant l’expression formelle:

a^’_kl = a_kl -

si le pivot est a_ij

le nouveau terme a^’_kl

l’ancien a_kl.

Appliquons ces 3 rÈgles à l’exemple, nous abtenons le nouveau tableau suivant du Simplexe, correspondent à la premiÈre itération:

Chaque terme de ce second tableau a été calculé en appliquant les trois rÈgles rappelées ci-dessus.

Quelle est l’interprétation de ce second tableau du Simplexe?

Il correspond au passage de la solution de base origine des coordonnées à la solution de base correspondant au sommet du polygone situé sur l’axe x₂ pour lequel nous lisons dans le tableau:

x₁ = 0 (variable hors-base)

x₂ = 8

x₄ = 1 (premiÈre variable d’écart)

x₅ = 26 (deuxiÈme variable d’écart)

Ce point correspond au sommet A de la solution géométrique.

Le tableau nous donne en outré la nouvelle valeur,changée de signe, de la fonction économique, soit f = 32.

Tout ceci est aisément verifiable.

Nous venons d’effectuer un pas du calcul du Simplexe correspondent à la premiÈre itération. Pour l’itération suivante, on procÈdera de mÊme.

Cette fois-ci, la variable entrante sera la variable x₁ (premier critÈre du Simplexe: plus fort coefficient de la fonction économique) et la variable sortante x₄ car la division des termes constants (8, 1, 26) respectivement par les coefficients de la colonne x₁(1/3, 1/3, 4) donne le coefficient de x₄ comme celui de la valeur la plus faible (deuxiÈme critÈre du Simplexe).

Le pivot est donc 1/3 (croisement de la colonne x₁ avec la ligne x₄).

D’oÙ le nouveau tableau du Simplexe correspondant à la deuxiÈme itération:

Qui correspond à la nouvelle solution de base:

x₁ = 3

x₂ = 7

x₃ = 0 variable hors base

x₄ = 0 variable hors base

x₅ = 14 variable d’écart

f = 37

Ce point correspond au sommet B de la solution géométrique.

Une nouvelle iteration est possible tant que l’un des coefficients de la function économique a une valeur positive. C’est le cas ici.

Une nouvelle application de l’algorithme conduit au nouveau tableau:

qui correspond à la solution de base:

x₁ = 7

x₂ = 5

x₃ = 2 variable d’écart

x₄ = 0 variable hors base

x₅ = 0 variable hors base

Ce point correspond au point C de la solution géométrique, c’est-à-dire à l’optimum cherché.

Nous constatons qu’aucun coefficient C n’est plus positif, le calcul est donc bien terminé.

La valeur de la function économique est f = 41 correspondant au maximum.

Par exemple, avec trois machines et trois moyens, nous aurons le tableau suivant:

Alors , les limitations de capacités se traduiront par le systÈme d’inéquations:

x₁t₁₁ + x₂t₂₁ + x₃t₃₁ ≤ C₁

x₁t₁₂ + x₂t₂₂ + x₃t₃₂ ≤ C₂

x₁t₁₃ + x₂t₂₃ + x₃t₃₃ ≤ C₃

D’autre part, si la marge degage par P₁ este m₁, P₂m₂, P₃m₃: la marge totale pour le programme x₁ x₂ x₃ est

M = x₁ m₁ + x₂ m₂ + x₃ m₃

que nous devons maximiser.

Il s’agit bien là d’un problÈme de programmation linéaire qui relÈve donc de la Méthode du Simplexe.